package middle;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组nums，返回 nums中最长等差子序列的长度。
 *
 * 回想一下，nums 的子序列是一个列表nums[i1], nums[i2], ..., nums[ik] ，
 * 且0 <= i1 < i2 < ... < ik <= nums.length - 1。
 * 并且如果seq[i+1] - seq[i](0 <= i < seq.length - 1) 的值都相同，那么序列seq是等差的。
 * 示例 1：
 *
 * 输入：nums = [3,6,9,12]
 * 输出：4
 * 解释： 
 * 整个数组是公差为 3 的等差数列。
 *
 * 示例 2：
 *
 * 输入：nums = [9,4,7,2,10]
 * 输出：3
 * 解释：
 * 最长的等差子序列是 [4,7,10]。
 *
 * 链接：https://leetcode.cn/problems/longest-arithmetic-subsequence
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class LongestArithmeticSubsequence {
    class Solution {
        public int longestArithSeqLength(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            /**
             * 定义dp数组
             * */
            int[][] dp = new int[nums.length][nums.length];

            /**
             * 状态转移
             * 对于差值为d的等差数列，有 k + d = j, j + d = i
             * 则 k + 2d = i
             * 故得出 2j - i = 2k+2d - k - 2d = k
             * */
            int ans = 0;
            for (int j = 0; j < nums.length; j++) {
                for (int i = j+1; i < nums.length; i++) {
                    int k = 2*nums[j] - nums[i];
                    if (map.containsKey(k)) {
                        dp[j][i] = dp[map.get(k)][j] + 1;
                    }
                    ans = Math.max(ans, dp[j][i]);
                }
                // ps: map的初始化一定要放到循环中，因为nums数组不排除有相等的数。需要先计算一个放一个
                map.put(nums[j], j);
            }
            return ans + 2;
        }
    }
}
